package basic.study.leetcode;

import java.util.Stack;

/**
 * @ClassName Hard85
 * @Description 最大矩形
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/25 15:39
 * @Version 1.0
 */
public class Hard85 {
    /**
     * 动态规划 - 使用柱状图的优化暴力方法
     * https://leetcode-cn.com/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode/
     */
    class Solution {
        public int maximalRectangle(char[][] matrix) {
            if (matrix.length == 0) return 0;
            int maxarea = 0;
            int[][] dp = new int[matrix.length][matrix[0].length];

            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == '1') {
                        dp[i][j] = j == 0?1:dp[i][j-1] + 1;
                        int width = dp[i][j];
                        for (int k = i; k >= 0; k--) {
                            width = Math.min(width, dp[k][j]);
                            maxarea = Math.max(maxarea, width*(i-k+1));
                        }
                    }
                }
            }
            return maxarea;
        }
    }
    /**
     * 使用柱状图 - 栈
     */
    class Solution1 {
        public int maximalRectangle(char[][] matrix) {
            if (matrix.length == 0) return 0;
            int maxarea = 0;
            int[] dp = new int[matrix[0].length];

            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    //构建柱状图
                    dp[j] = matrix[i][j] == '1'? dp[j]+1: 0;
                }
                //求柱状图最大面积
                maxarea = Math.max(maxarea, leetcode84(dp));
            }
            return maxarea;
        }

        private int leetcode84(int[] heights) {
            int[] left = new int[heights.length];
            int[] right = new int[heights.length];
            Stack<Integer> stack = new Stack<>();

            for (int i = 0; i < heights.length; i++) {
                while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                    stack.pop();
                }
                left[i] = (stack.isEmpty())?-1:stack.peek();
                stack.push(i);
            }
            stack.clear();
            for (int i = heights.length-1; i >= 0; i--) {
                while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                    stack.pop();
                }
                right[i] = (stack.isEmpty())?heights.length:stack.peek();
                stack.push(i);
            }
            int ans = 0;
            for (int i = 0; i < heights.length; i++) {
                ans = Math.max(ans, (right[i]-left[i]-1)*heights[i]);
            }
            return ans;
        }
    }
}
